# 哈希表或者快慢指针+反转链表
# 需要考虑全部删除的情况
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
#
# @param head ListNode类
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head ):
        # write code
        all_num = list()
        twice = list()
        if not head:
            return None
        else:
            cur = head
            while cur:
                if cur.val not in all_num:
                    all_num.append(cur.val)
                else:
                    twice.append(cur.val)
                cur = cur.next
            # 先删除后面的那一个，前面的删除指针就没了哎
            prev, cur = head, head.next
            while cur:
                if cur.val in twice:
                    cur = cur.next
                    prev.next = cur
                else:
                    prev = cur
                    cur = cur.next
            # 此时的cur是head.next直接输出会少一位，应该输出head
            # 上一步只跳过了下一个因为cur是下一个
            # 再删除掉前一个的
            if head and head.val in twice:
                head = head.next
            return head